#pragma once
#include "hSomeTool.h"
#include "hHashVector.h"

template <typename Key, typename Val, size_t N>
struct _hHashVectorNode
{
	std::pair<uint8_t, Key> _idx;
	_hHashVectorNode<Key, Val, N>* _parent = NULL;

	const Key _key;
	Val* _val = NULL;
	_hHashVectorNode<Key, Val, N>** _pNext = NULL;

	_hHashVectorNode(Key key = 0);
	std::ostream& fillDebug(std::ostream& os, uint8_t idx = 0) const;

	_hHashVectorNode* getNext();

	size_t calcNum() const;
	size_t calcCapacity() const;
	size_t calcSize() const;
	size_t calcMemNum() const;
	size_t calcMemSize() const;

	template<typename... Args>
	Val* addVal(Args... args);
	template<typename... Args>
	_hHashVectorIterator<Key, Val> emplaceCallBack(hHashVector<Key, Val>* pVec, bool isLst, Key k, Args... args);
	template<typename... Args>
	_hHashVectorIterator<Key, Val> findCallBack(_hHashVectorIterator<Key, Val>& it, bool isLst, Key k);

	std::pair<Key, bool> hashFromKey(Key k) const;
	Key hashToKey(Key idx) const;
};

template <typename Key, typename Val>
class _hHashVectorIterator
{
	hHashVector<Key, Val>* _pVec = NULL;
	_HashVectorNode<Key, Val>* _pNode = NULL;

	friend hHashVector<Key, Val>;
	friend _HashVectorNode<Key, Val>;
public:
	Val& operator*();
	_hHashVectorIterator& operator++();
	_hHashVectorIterator operator++(int);

	bool operator==(const _hHashVectorIterator& other) { return _pVec == other._pVec && _pNode == other._pNode; }
	bool operator!=(const _hHashVectorIterator& other) { return !(*this == other); }
	operator bool() const { return _pVec; }
};

template<typename Key, typename Val>
typename hHashVector<Key, Val>::Iter hHashVector<Key, Val>::find(Key k)
{
	Iter it;
	it._pVec = this;
	return _node.findCallBack(it, false, k);
}

template <typename Key, typename Val>
typename hHashVector<Key, Val>::Iter hHashVector<Key, Val>::begin()
{
	Iter it;
	it._pVec = this;

	do 
	{
		if (_node._val)
		{
			it._pNode = &_node;
			break;
		}
		
		it._pNode = _node.getNext();
	} while (0);

	return it;
}

template <typename Key, typename Val>
typename hHashVector<Key, Val>::Iter hHashVector<Key, Val>::end()
{
	Iter it;
	it._pVec = this;
	return it;
}

template<typename Key, typename Val>
inline std::ostream& hHashVector<Key, Val>::fillDebug(std::ostream& os, uint8_t idx) const
{
	os << "(" << _node.calcNum() << "/" << _node.calcCapacity() << "/" << _node.calcMemNum() << ")(" << _node.calcMemSize() << "/" << _node.calcSize() << ")";

	return _node.fillDebug(os, idx);
}

template<typename Key, typename Val, size_t N>
_hHashVectorNode<Key, Val, N>::_hHashVectorNode(Key key) : _key(key)
{
	static_assert(std::is_integral<Key>::value, "Integral required");

	std::cout << "key=" << _key << std::endl;
}

template <typename Key, typename Val, size_t N>
std::ostream& _hHashVectorNode<Key, Val, N>::fillDebug(std::ostream& os, uint8_t idx) const
{
	os << (size_t)_idx.first << "/"  << (size_t)_idx.second << "/" << _key << ",{";
	if (!_pNext)
		return os << "}";

	bool first = true;
	for (size_t i = 0; i < PowN<2, N>; ++i)
	{
		if (first) first = false;
		else os << ",";

		_hHashVectorNode<Key, Val, N>* pNext = _pNext[i];
		if (pNext)
		{
			os << std::endl;
			os << std::string(idx + 1, '\t') << "[" << i << "]";
			pNext->fillDebug(os, idx + 1);
		}
		else
			os << "[" << i << "]" << "NULL";
	}
	return os << "}";
}

template<typename Key, typename Val, size_t N>
inline _hHashVectorNode<Key, Val, N>* _hHashVectorNode<Key, Val, N>::getNext()
{
	if (_pNext)
	{
		for (Key i = 0; i < PowN<2, N>; ++i)
		{
			if (!_pNext[i])
				continue;

			if (_pNext[i]->_val)
				return _pNext[i];
			else
				return _pNext[i]->getNext();
		}
	}

	if (!_parent || !_idx.first || !_key)
		return NULL;

	_hHashVectorNode<Key, Val, N>* pParent = _parent;
	Key iBeg = _idx.second + 1;
	while (pParent)
	{
		for (Key i = iBeg; i < PowN<2, N>; ++i)
		{
			if (!pParent->_pNext[i])
				continue;

			if (pParent->_pNext[i]->_val)
				return pParent->_pNext[i];
			else
				return pParent->_pNext[i]->getNext();
		}

		iBeg = pParent->_idx.second + 1;
		pParent = pParent->_parent;
	}

	return NULL;
}

template<typename Key, typename Val, size_t N>
inline size_t _hHashVectorNode<Key, Val, N>::calcNum() const
{
	size_t num = _val ? 1 : 0;

	if (!_pNext)
		return num;

	for (size_t i = 0; i < PowN<2, N>; ++i)
	{
		if (_pNext[i])
			num += _pNext[i]->calcNum();
	}

	return num;
}

template<typename Key, typename Val, size_t N>
inline size_t _hHashVectorNode<Key, Val, N>::calcCapacity() const
{
	size_t num = 1;

	if (!_pNext)
		return num;

	for (size_t i = 0; i < PowN<2, N>; ++i)
	{
		if (_pNext[i])
			num += _pNext[i]->calcCapacity();
	}

	return num;
}

template<typename Key, typename Val, size_t N>
inline size_t _hHashVectorNode<Key, Val, N>::calcSize() const
{
	size_t size = sizeof(*this);

	if (!_pNext)
		return size;

	size += std::ratio_multiply<std::ratio<PowN<2, N>>, std::ratio<sizeof(_pNext[0])>>::num;
	for (size_t i = 0; i < PowN<2, N>; ++i)
	{
		if (_pNext[i])
			size += _pNext[i]->calcSize();
	}

	return size;
}

template<typename Key, typename Val, size_t N>
inline size_t _hHashVectorNode<Key, Val, N>::calcMemNum() const
{
	if (!_pNext)
		return 0;

	size_t size = PowN<2, N>;
	for (size_t i = 0; i < PowN<2, N>; ++i)
	{
		if (_pNext[i])
			size += _pNext[i]->calcMemNum();
	}

	return size;
}

template<typename Key, typename Val, size_t N>
inline size_t _hHashVectorNode<Key, Val, N>::calcMemSize() const
{
	if (!_pNext)
		return 0;

	size_t size = std::ratio_multiply<std::ratio<PowN<2, N>>, std::ratio<sizeof(_pNext[0])>>::num;
	for (size_t i = 0; i < PowN<2, N>; ++i)
	{
		if (_pNext[i])
			size += _pNext[i]->calcMemSize();
	}

	return size;
}

template<typename Key, typename Val, size_t N>
inline std::pair<Key, bool> _hHashVectorNode<Key, Val, N>::hashFromKey(Key k) const
{
	Key decK = k - (_key >> (_idx.first * N) & 1 ? 2 : 1);
	return std::make_pair((Key)(decK & BitN<N>), decK < PowN<2, N>);
}

template<typename Key, typename Val, size_t N>
inline Key _hHashVectorNode<Key, Val, N>::hashToKey(Key idx) const
{
	return (idx + 1) * (1 << (_idx.first * N)) + _key;
}

template<typename Key, typename Val, size_t N>
template<typename ...Args>
Val* _hHashVectorNode<Key, Val, N>::addVal(Args ...args)
{
	if (_val)
		return _val;

	_val = new Val(args...);
	return _val;
}

template<typename Key, typename Val, size_t N>
template<typename ...Args>
_hHashVectorIterator<Key, Val> _hHashVectorNode<Key, Val, N>::emplaceCallBack(hHashVector<Key, Val>* pVec, bool isLst, Key k, Args ...args)
{
	if (!k || isLst)
	{
		addVal(args...);
		_hHashVectorIterator<Key, Val> it;
		it._pVec = pVec;
		it._pNode = this;
		return it;
	}

	if (!_pNext)
		_pNext = new _hHashVectorNode<Key, Val, N> * [PowN<2, N>]();

	auto hashPr = hashFromKey(k);
	if (!_pNext[hashPr.first])
		_pNext[hashPr.first] = new _hHashVectorNode<Key, Val, N>(hashToKey(hashPr.first));

	assert(_pNext[hashPr.first]);
	_hHashVectorNode<Key, Val, N>& nxtNd = *_pNext[hashPr.first];
	nxtNd._idx.first = _idx.first + 1;
	nxtNd._idx.second = hashPr.first;
	nxtNd._parent = this;

	return nxtNd.emplaceCallBack(pVec, hashPr.second, k >> N, args...);
}

template<typename Key, typename Val, size_t N>
template<typename ...Args>
_hHashVectorIterator<Key, Val> _hHashVectorNode<Key, Val, N>::findCallBack(_hHashVectorIterator<Key, Val>& it, bool isLst, Key k)
{
	if (!k || isLst)
	{
		it._pNode = this;
		return it;
	}

	if (!_pNext)
		return it;

	auto hashPr = hashFromKey(k);
	if (!_pNext[hashPr.first])
		return it;

	return _pNext[hashPr.first]->findCallBack(it, hashPr.second, k >> N);
}

template <typename Key, typename Val>
Val& _hHashVectorIterator<Key, Val>::operator*()
{
	assert(_pVec);
	assert(_pNode);
	assert(_pNode->_val);
	return *_pNode->_val;
}

template <typename Key, typename Val>
_hHashVectorIterator<Key, Val>& _hHashVectorIterator<Key, Val>::operator++()
{
	assert(_pVec);
	assert(_pNode);
	assert(_pNode->_val);
	_pNode = _pNode->getNext();
	return *this;
}

template <typename Key, typename Val>
_hHashVectorIterator<Key, Val> _hHashVectorIterator<Key, Val>::operator++(int)
{
	assert(_pVec);
	assert(_pNode);
	assert(_pNode->_val);
	_hHashVectorIterator<Key, Val> it;
	it._pVec = _pVec;
	it._pNode = _pNode;
	_pNode = _pNode->getNext();
	return it;
}